package everyday;

/**
 * @author zhangmin
 * @create 2022-04-28 9:42
 *
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 *
 * dfs,将与边界相邻的O标记为A，然后将所有的剩下的O变成X，A变成O
 */
public class solve130 {

    void dfs(char[][] board,int i,int j){
        int m=board.length,n=board[0].length;
        if (i<0||i>=m||j<0||j>=n||board[i][j]!='O'){
            return;
        }
        board[i][j]='A';
        dfs(board,i,j+1);
        dfs(board,i+1,j);
        dfs(board,i,j-1);
        dfs(board,i-1,j);
    }
    public void solve(char[][] board) {
        //对着边界上的每个位置进行dfs
        int m=board.length,n=board[0].length;
        for (int i = 0; i < n; i++) {
            dfs(board,0,i);
            dfs(board,m-1,i);
        }
        for (int i = 0; i < m; i++) {
            dfs(board,i,0);
            dfs(board,i,n-1);
        }
        //将其中剩余的O变为X，并将A变为O
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j]=='O'){
                    board[i][j]='X';
                }else if (board[i][j]=='A'){
                    board[i][j]='O';
                }
            }
        }
    }
}
